package leetcode.code1728;

public class Solution5 extends Solution1728 {
	int rows;
	int cols;
	int[][] grids;

	int ROAD = 1, WALL = 0, CAT = 2, MOUSE = 3, FOOD = 4;
	int jumpCat;
	int jumpMouse;
	int XFOOD;
	int YFOOD;

	boolean WINMOUSE = true;
	boolean WINCAT = false;
	Boolean[][][][][] winner;
	boolean[][][] m2, c2;
	int times;

	@Override
	public boolean canMouseWin(String[] grid, int catJump, int mouseJump) {
		this.jumpCat = catJump;
		this.jumpMouse = mouseJump;
		rows = grid.length;
		cols = grid[0].length();
		grids = new int[rows][cols];
		int xmouse = 0, ymouse = 0;
		int xcat = 0, ycat = 0;
		for (int i = 0; i < rows; i++) {
			char[] g = grid[i].toCharArray();
			for (int j = 0; j < cols; j++) {
				char c = g[j];
				if (c == '.') {
					grids[i][j] = ROAD;
				} else if (c == '#') {
					grids[i][j] = WALL;
				} else if (c == 'C') {
					grids[i][j] = CAT;
					xcat = i;
					ycat = j;
				} else if (c == 'M') {
					grids[i][j] = MOUSE;
					xmouse = i;
					ymouse = j;
				} else if (c == 'F') {
					grids[i][j] = FOOD;
					this.XFOOD = i;
					this.YFOOD = j;
				}
			}
		}
		times = 8 * 8 * 2;
		c2 = new boolean[rows][cols][times + 1];
		m2 = new boolean[rows][cols][times + 1];
		c2[xcat][ycat][0] = true;
		m2[xmouse][ymouse][0] = true;
		winner = new Boolean[rows][cols][rows][cols][times + 1];
		boolean ans = this.mouseMove(0, xmouse, ymouse, xcat, ycat);
		return ans;
	}

	// 右，左，下，上
	int[] direction = new int[] { 0, 1, 0, -1, 1, 0, -1, 0 };

	private boolean mouseMove(int round, int xmouse, int ymouse, int xcat, int ycat) {
		if (winner[xmouse][ymouse][xcat][ycat][round] != null) {
			return winner[xmouse][ymouse][xcat][ycat][round];
		}
		if (round >= times || (xmouse == xcat && ymouse == ycat) || (XFOOD == xcat && YFOOD == ycat)) {
			winner[xmouse][ymouse][xcat][ycat][round] = false;
			return false;
		}
		if (XFOOD == xmouse && YFOOD == ymouse) {
			winner[xmouse][ymouse][xcat][ycat][round] = true;
			return true;
		}
		for (int d = 0; d < 8; d += 2) {
			for (int i = 0; i <= this.jumpMouse; i++) {
				int nextx = xmouse + direction[d] * i;
				int nexty = ymouse + direction[d + 1] * i;
				if (nextx < 0 || nexty < 0 || nextx >= rows || nexty >= cols || this.grids[nextx][nexty] == WALL) {
					break;
				}
				if (!m2[nextx][nexty][round]) {
					m2[nextx][nexty][round] = true;
					boolean ans = this.catMove(round + 1, nextx, nexty, xcat, ycat);
					m2[nextx][nexty][round] = false;
					if (!ans) {
						winner[xmouse][ymouse][xcat][ycat][round] = true;
						return true;
					}
				}
			}
		}
		winner[xmouse][ymouse][xcat][ycat][round] = false;
		return false;
	}

	private boolean catMove(int round, int xmouse, int ymouse, int xcat, int ycat) {
		if (winner[xmouse][ymouse][xcat][ycat][round] != null) {
			return winner[xmouse][ymouse][xcat][ycat][round];
		}
		if (round >= times || (xmouse == xcat && ymouse == ycat) || (XFOOD == xcat && YFOOD == ycat)) {
			winner[xmouse][ymouse][xcat][ycat][round] = true;
			return true;
		}
		if (XFOOD == xmouse && YFOOD == ymouse) {
			winner[xmouse][ymouse][xcat][ycat][round] = false;
			return false;
		}
		for (int d = 0; d < 8; d += 2) {
			for (int i = 0; i <= this.jumpCat; i++) {
				int nextx = xcat + direction[d] * i;
				int nexty = ycat + direction[d + 1] * i;
				if (nextx < 0 || nexty < 0 || nextx >= rows || nexty >= cols || this.grids[nextx][nexty] == WALL) {
					break;
				}
				if (!c2[nextx][nexty][round]) {
					c2[nextx][nexty][round] = true;
					boolean ans = this.mouseMove(round + 1, xmouse, ymouse, nextx, nexty);
					c2[nextx][nexty][round] = false;
					if (!ans) {
						winner[xmouse][ymouse][xcat][ycat][round] = true;
						return true;
					}
				}
			}
		}
		winner[xmouse][ymouse][xcat][ycat][round] = false;
		return false;
	}

	public static void main(String[] args) {
		Solution5 so = new Solution5();
		so.debug11();
		so.debug10();
		so.debug7();
		so.debug9();
		so.debug8();
		so.debug6();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
		so.debug5();

	}

}
